package com.sfx.算法专题.动态规划.完全背包;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-07-16
 * Time: 19:49
 */
public class Code_3_change {
    static class Solution {
        public int change(int amount, int[] coins) {
            //1.硬币任意选择,不超过总金额j的硬币组合数为dp[j]
            int[] dp = new int[amount+1];
            //2.状态转移方程为 :
            //对于第i个硬币你选还是不选
            //                  不选    选择
            // dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1)
            //3.dp数组初始化
            dp[0] = 1;
            for(int i =1;i<=coins.length;++i) {
                for(int j = coins[i-1];j<=amount;++j) {
                    dp[j] += dp[j-coins[i-1]];
                }
            }
            return dp[amount];
        }
    }
}